大数据方法论之网页消重的Map-Reduce算法

当你爬取了大量的网页，里面肯定有很多重复的内容，这些重复的内容需要去重来解决。

一个著名的算法就是SimHash算法。

通用的去重算法框架如图所示(图来自互联网)

对于一篇文档，首先要抽取出能代表这篇文章内容的特征，当然特征数目肯定是很多的，如果比较两篇文章的所有特征，太费时间了，所以要对特征进行一定的运算，称为文档指纹，指纹就像人的指纹一样，虽然信息量不大，相对比较容易相互比较，但是能够代表区分不同人的信息。最后就是基于指纹进行相似度计算，相似度大的，则为文档重复，相似度小的，则文档不重复。

对于SimHash来讲，计算方法如下：

1、分词，讲文本分词形成这个文章的特征单词。最后形成去掉停词之类的单词序列，并统计每个词出现的数目tf作为权重

2、hash，通过hash算法把每个词变成hash值，这里以8位hash值为例子。

3、加权合并，通过 2步骤的hash生成结果中的每一位，乘以权重，然后加起来，形成权值求和的向量

4、降维，把3步算出来的 向量变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。

上面的指纹数目使用8位做简单的演示，真实的使用中往往使用64bits指纹， <= 3bit 不同算相似。

然而在64位中逐个比较，直到找出3个不同位来，计算量还是很大的，所以就有了如下的SimHash的索引结构。

将64位的二进制串等分成四块，每块16位，将所有的文章的simhash保存四份，分别保存在四个Table里面，在第一个Table里面，第一个16位在前面，第二个Table里面，第二个16位在前面，以此类推。

来了一篇新的文档的时候，也将64位分成四份，变成如图红色的四个序列。

首先采用精确匹配的方式查找前16位，如果在四个Table中都匹配不中，则说明至少有四位是不同的，已经不相似。

如果和其中一个Table比较中了，然后在Table中再进行比较。

下面我们来看如何使用Map-Reduce来解决这个问题。

假设：有1T非重复的已有网页集合 SimHashDb <url, simhash, content>，新来100万网页parse_text。

首先要做的事情是新来的100万网页内部去重，可以分成100个map任务，每个任务1万个网页。

对于每个网页求simhash为64位，然后将这个simhash加到四个Table里面，并且partition的时候，是根据四个table进行partiton的。

在Reduce的时候，有四个Table，所以是四个Reduce，每个Table的key是前16位，有相同的Table Key的都在一个list里面，在这个list里面比较是否差异超过3位，超过则false，不超过则true。

最终输出的是四个partition，每个partition里面都会记录每篇文章isdup为true还是false，为true，则说明100万以内就重复了，false则还需要进一步去重。

最后100万数据要和1T的数据进行去重了，这里的算法有一个小技巧，就是到底是100万把1T数据过一遍，还是1T数据把100万过一遍。

对于普通的算法，当然是1T变成某种索引结构放在那里，100万分别和1T去比较，但是map-reduce里面，如果这样会发现100万的并发度太低，并且并发的任务如果都去统一的1T里面去比较，相当于虽然任务分开了，但是有一个统一的瓶颈点，其实并没有分布式的去计算，虽然分成了100个任务，但是大家都去调用同一个url地址。

但是1T的数据是全量数据，是不可能加载到内存里面的，也不肯能有几个任务就复制成几份。

但是思路一旦反过来就可以了，我们让全量去过增量，因为增量是很小的，加载到内存或者复制多份代价都不大，而全量的数据量大，适合分任务去执行，能够并发的起来。

于是我们将全量1T进行split来分成map任务，64M一块，这样并发任务会很

多，大大提高的执行速度。

对于每个map任务，看到的都是增量的四个Table的全部。这64M的全量里面的文档放在增量的四个Table中进行比较。对于增量的文档，如果重复则标记true，否则为false.

Reduce的时候，处理的还是增量的部分，全量的只是过了一下，其实没有动，增量的部分相当于复制成了多份，在每个split里面进行比较，最后汇总的时候，有一个是重复的，则就为重复了。

不重复的部分汇总到全量里面去。